//*************************************************************************************
// Helper functions for bitboard operations
//*************************************************************************************

#include "Stdafx.h"
#include "Engine.h"


// internal arrays
int8 LSBarray[256];
int8 MSBarray[256];
int8 BitsInWord[65536];
uint32 RevWord[65536];

//*************************************************************************************
// Initialization
//*************************************************************************************

// array initialization routine
void InitBool()
{

	int i,j;

	// initialize array for "LSB" 
	for(i=0;i<256;i++)
	{
		if(i&1) {LSBarray[i]=0;continue;}
		if(i&2) {LSBarray[i]=1;continue;}
		if(i&4) {LSBarray[i]=2;continue;}
		if(i&8) {LSBarray[i]=3;continue;}
		if(i&16) {LSBarray[i]=4;continue;}
		if(i&32) {LSBarray[i]=5;continue;}
		if(i&64) {LSBarray[i]=6;continue;}
		if(i&128) {LSBarray[i]=7;continue;}
		LSBarray[i]=-1;
	}

	// initialize array for "MSB" 
	for(i=0;i<256;i++)
	{
		if(i&128) {MSBarray[i]=7;continue;}
		if(i&64) {MSBarray[i]=6;continue;}
		if(i&32) {MSBarray[i]=5;continue;}
		if(i&16) {MSBarray[i]=4;continue;}
		if(i&8) {MSBarray[i]=3;continue;}
		if(i&4) {MSBarray[i]=2;continue;}
		if(i&2) {MSBarray[i]=1;continue;}
		if(i&1) {MSBarray[i]=0;continue;}
		MSBarray[i]=-1;
	}

	// initialize bitsinword, the number of bits in a word
	for(i=0;i<65536;i++)
		BitsInWord[i] = RecBitCount((uint32)i);

	// initialize revword, the reverse of a word.
	for(i=0;i<65536;i++)
	{
		RevWord[i]=0;
		for(j=0;j<16;j++)
		{
			if(i&(1<<j))
			RevWord[i] +=1<<(15-j);
		}
	}
}

//*************************************************************************************
// 32-bit versions
//*************************************************************************************

// index of least significant bit in the number
int LSB(uint32 x)
	{

	if(x&0x000000FF)
		return(LSBarray[x&0x000000FF]);
	if(x&0x0000FF00)
		return(LSBarray[(x>>8)&0x000000FF]+8);
	if(x&0x00FF0000)
		return(LSBarray[(x>>16)&0x000000FF]+16);
	if(x&0xFF000000)
		return(LSBarray[(x>>24)&0x000000FF]+24);
	return -1;
}


// index of most significant bit in the number
int MSB(uint32 x)
	{
	if(x&0xFF000000)
		return(MSBarray[(x>>24)&0xFF]+24);
	if(x&0x00FF0000)
		return(MSBarray[(x>>16)&0xFF]+16);
	if(x&0x0000FF00)
		return(MSBarray[(x>>8)&0xFF]+8);
	return(MSBarray[x&0xFF]);
}


// reverts bits in the number
uint32 Revert(uint32 n)
{
	return (RevWord[HiWord(n)] + (RevWord[LoWord(n)]<<16));
}


// table of bit count in the number
int BitCount(uint32 n)
{
	return (BitsInWord[n&0x0000FFFF]+BitsInWord[(n>>16)&0x0000FFFF]);
}


// counts the number of bits in the number
int RecBitCount(uint32 n)
{
	int r=0;
	while(n)
		{
		n=n&(n-1);
		r++;
		}
	return r;
}

//*************************************************************************************
// 64-bit versions
//*************************************************************************************

// index of least significant bit in the number
int LSB64(uint64 x)
	{

	if(x&0x00000000000000FF)
		return(LSBarray[x&0x000000FF]);
	if(x&0x000000000000FF00)
		return(LSBarray[(x>>8)&0x000000FF]+8);
	if(x&0x0000000000FF0000)
		return(LSBarray[(x>>16)&0x000000FF]+16);
	if(x&0x00000000FF000000)
		return(LSBarray[(x>>24)&0x000000FF]+24);
	if(x&0x000000FF00000000)
		return(LSBarray[(x>>32)&0x000000FF]+32);
	if(x&0x0000FF0000000000)
		return(LSBarray[(x>>40)&0x000000FF]+40);
	if(x&0x00FF000000000000)
		return(LSBarray[(x>>48)&0x000000FF]+48);
	if(x&0xFF00000000000000)
		return(LSBarray[(x>>56)&0x000000FF]+56);
	return -1;
}

// index of most significant bit in the number
int MSB64(uint64 x)
	{
	if(x&0xFF00000000000000)
		return(MSBarray[(x>>56)&0xFF]+56);
	if(x&0x00FF000000000000)
		return(MSBarray[(x>>48)&0xFF]+48);
	if(x&0x0000FF0000000000)
		return(MSBarray[(x>>40)&0xFF]+40);
	if(x&0x000000FF00000000)
		return(MSBarray[(x>>32)&0xFF]+32);
	if(x&0x00000000FF000000)
		return(MSBarray[(x>>24)&0xFF]+24);
	if(x&0x0000000000FF0000)
		return(MSBarray[(x>>16)&0xFF]+16);
	if(x&0x000000000000FF00)
		return(MSBarray[(x>>8)&0xFF]+8);
	return(MSBarray[x&0xFF]);
}

// the number of bits
int BitCount64(uint64 n)
{
	return (BitsInWord[n&0x0000FFFF] + BitsInWord[(n>>16)&0x0000FFFF]  
			+ BitsInWord[(n>>32)&0x0000FFFF]  + BitsInWord[(n>>48)&0x0000FFFF]);
}


//*************************************************************************************
// Template switching
//*************************************************************************************

// LSB - the least significant bit
template<> int LSBxx<BitBoard>(typename BitBoard::value_type x)
{
	return LSB(x);
}

template<> int LSBxx<BitBoard64>(typename BitBoard64::value_type x)
{
	return LSB64(x);
}


// MSB - the most significant bit
template<> int MSBxx<BitBoard>(typename BitBoard::value_type x)
{
	return MSB(x);
}

template<> int MSBxx<BitBoard64>(typename BitBoard64::value_type x)
{
	return MSB64(x);
}


// The number of bits 
template<> int BitCountXX<BitBoard>(typename BitBoard::value_type x)
{
	return BitCount(x);
}

template<> int BitCountXX<BitBoard64>(typename BitBoard64::value_type x)
{
	return BitCount64(x);
}


// Revert - reversing the bits in the UINT32 or UINT64
template<> typename BitBoard::value_type RevertXX<BitBoard>(typename BitBoard::value_type x)
{
	return Revert(x);
}

template<> typename BitBoard64::value_type RevertXX<BitBoard64>(typename BitBoard64::value_type x)
{
	return Revert64<50>(x);
}
